package com.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution17 {

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        List<Integer> path = new ArrayList<>();
        return getPath(root, path, targetSum);
    }

    public boolean getPath(TreeNode root, List<Integer> path, int target) {
        path.add(root.val);
        if (root.left == null && root.right == null) {
            int sum = 0;
            for (int i : path) {
                sum += i;
            }
            if (sum == target) return true;
            else return false;
        }
        boolean l = false, r = false;
        if (root.left != null) {
            l = getPath(root.left, path, target);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            r = getPath(root.right, path, target);
            path.remove(path.size() - 1);
        }
        return r || l;
    }
}
